The present invention relates to a variable length code conversion system which can quickly recover a synchronized state when a bit error occurs.
A variable length code which can transmit information with high efficiency has the combination of 0 and 1. The bit length of that variable length code is determined depending upon the probability of each symbol. When a bit error occurs, a receiver side misses an end of a codeword, a decoding error happens as shown in the table 1 and FIG. 9. That state is called an asynchronous state.
TABLE 1 ______________________________________ Symbol Occurrence probability Codeword ______________________________________ A 0.3 00 B 0.3 01 C 0.2 10 D 0.1 110 E 0.1 111 ______________________________________
A short codeword is designated for a symbol having a high occurrence probability.
In FIG. 9, when the code "BAECACBBAD" is transmitted, and the first bit is in error, the codeword "01" of "B" is received as "11", then, the receiver side recognizes the received signal as "DBEABACCBC". Similarly, when the word "BAECACBDBA" is transmitted, and the first bit is in error, the received word is "DBEABAEAC" and a bit "0" remains undercoded.
An asynchronous state occurs because all the bits which makes up a codeword are not always decoded, but a part of the bits remain as a prefix of another codeword. This is shown in a tree of FIG. 7 as a location of a node. A prefix is defined as a part of a codeword beginning from the head of the codeword, and a suffix is defined as a rear part of a codeword from an intermediate bit to the end bit of the codeword. As an example in table 1, the bit train "11" is a prefix for the symbols D and E, and the bit train "10" is a suffix for the symbol D.
An asynchronous state propagates to succeeding codewords.
In order to stop the asynchronous state, and/or a transmission error, an error correcting code has been used.
However, an error correcting code has the disadvantage that some additional bits must be attached for detecting and/or correcting a bit error, and those additional bits decrease the transmission efficiency. Therefore, a code which has no additional bit, and can recover quickly from an asynchronous state, has been desired.
Conventionally, in order to obtain quick recovery from an asynchronous state, the sum of the probability of synchronizing codewords is as large as possible. The synchronizing codeword is defined as a codeword which recovers the synchronized state upon receipt of the codeword in any asynchronous state. A code which has a synchronizing codeword is called a synchronizing code, and a code which has no synchronized codeword is called a non-synchronizing code. A prior code which can recover quickly is described in the article (Bruce L. Montgomery and Julia Abrahams; "Synchronization of binary Source Codes", IEEE Trans. Inform. Theory, vol. IT-32, No. 6, Nov. 1986).
The basic idea of that article is now briefly described. It increases the number of the synchronizing codewords and the sum of the probability of the synchronizing codewords by adding a small number of bits to codewords which have small occurrence probability. In that system, a bit length vector L (n.sub.1, n.sub.2, .., n.sub.m) is defined for classifying the codewords for each length (n.sub.i is the number of codewords which have the length i), and a new code is generated for each case. (A) When an original code is a synchronizing code; (A-1) When no interval exists in elements of a bit length vector L; (no interval is defined so that n.sub.i &gt;0, i&gt;s; and n.sub.i =0, i&lt;s, for a given value s)
A codeword r.sub.i.sup.L,r in the condition that 2.ltoreq.L,r and j.gtoreq.r is defined so that the following three conditions are satisfied.
(1) r.sub.i.sup.L,r =a.sub.i 01.sub.r-l a.sub.i is a train of 0 and 1, including a null set. PA1 (2) 1.sub.k 0 is not a prefix for any k (k&gt;L-1). 1.sub.k 0 is a codeword comprising a consecutive k number of 1 followed by a single 0 (111.....110). PA1 (3) A codeword r.sub.i.sup.L,r which is shorter than j is not a prefix of r.sub.i.sup.L,r. PA1 (1) The code generation is impossible unless the bit length vector satisfies the particular conditions, irrespective of the recovery ability of the original code. PA1 (2) The process for the generation is complicated and must consider the nature of the bit length vector and whether the original code is a synchronized code or not. PA1 (3) An additional bit is attached for providing a synchronized codeword to an efficient codeword. The additional bits are usually more than two bits, and therefore, the transmission efficiency is decreased by the additional bits. PA1 (4) Because of the addition of bits, no recovery is sometimes possible. PA1 (5) The recovery ability is not always high, even if the sum of the probability of the synchronized codeword is large, since it does not consider the contribution by codewords except the synchronized code for the synchronization recovery.
The number of r.sub.i.sup.L,r which satisfies the above conditions is expressed as d.sub.j.sup.L,r. The new vector L' is generated from the bit length vector L according to the following rules. ##EQU1## where r.ltoreq.j.ltoreq.t-1) is satisfied, and 1.sub.k 0 (L+r-2.ltoreq.k.ltoreq.m) is synchronized codeword. The codeword 1.sub.m 0 is longer than the original codeword by one bit. Other codewords are defined according to the prefix condition (no codeword is a prefix of another codeword). (A-2) When an interruption exists in elements of a codeword vector L. Under the conditions that; ##EQU2##
The L' is obtained according to the above conditions, and the condition (2) of (A-1) is replaced by; ##EQU3## where r.ltoreq.j.ltoreq.t-1, is satisfied and 1.sub.k 0 (L+r-2.ltoreq.k.ltoreq.i.sub.2) is a synchronized codeword. The other codeword is determined according to the prefix condition.
(B) When an original code is an asynchronous code;
A few number of additional bits are adaptively attached to the original codeword, and the conditions A-1 and A-2 are used to convert an asynchronous code to a synchronized code.
However, the prior art has the following disadvantages.
The generation process depends upon the interruption of a bit length vector, and whether the original code is a synchronized code or not, therefore, no single process for generation is possible.
A code with additional bits may enter into an incomplete tree (FIG. 8), in which no code is designated to some branches. If a bit train which is not a prefix of any codeword is received, the recovery of the synchronization is impossible. For instance, when the bit train "1111" is received as a result of a bit error, the recovery in a receiver side is impossible for any arrival bit.